package main.java.LeetCode.SolutionVersionThree;




import main.java.LeetCode.CommonSolution.ListNode;
import main.java.LeetCode.CommonSolution.Node;
import main.java.LeetCode.CommonSolution.TreeNode;

import javax.print.DocFlavor;
import java.util.*;

@SuppressWarnings("ALL")
public class Solution {

    /**
     * 如何转化为01背包问题呢。
     * 假设加法的总和为x，那么减法对应的总和就是sum - x。
     * 所以我们要求的是 x - (sum - x) = target
     * x = (target + sum) / 2
     * 此时问题就转化为，装满容量为x的背包，有几种方法。
     * @param nums
     * @param target
     * @return
     */
    static final double ADDITION = -1;
    static final double SUBTRACTION = -2;
    static final double MULTIPLICATION = -3;
    static final double DIVISION = -4;
    static final double ANS = 24;


    public ListNode arrayToList(int[] arr){
        ListNode head = null;
        ListNode tail = null;

        for(int n:arr){
            if(head==null){
                head = new ListNode(n);
                tail = head;
                continue;
            }

            tail.next = new ListNode(n);
            tail = tail.next;
        }

        return head;
    }

    public void showList(ListNode head){
        while (head!=null){
            System.out.print(head.val+"->");
            head = head.next;
        }
        System.out.print("null");
    }

    public void showArray(int[] arr){
        for (int n:arr){
            System.out.print(n+" ");
        }
    }

    public void showArray(Integer[][] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
    }


    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum = sum + num;
        }
        if((sum+target)%2!=0)
            return 0;
        int cap = (sum+target)/2;
        int[] dp = new int[cap+1];
        dp[0] = 1;


        for(int num:nums){
            for(int i = dp.length-1;i>=1;i--){
                if(num>i)
                    break;
                dp[i] = dp[i-num]+1;
            }
        }
        return dp[cap];
    }

    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        int[] ZerosAndOnes = new int[2];
        for(String str:strs)
        {
            ZerosAndOnes = counterZerosAndOnes(str);
            int zero = ZerosAndOnes[0];
            int ones = ZerosAndOnes[1];

            for(int x = m;x>=0;x--)
            {
                for(int y = n;y>=0;y--)
                {
                    if(x>=zero&&y>=ones){
                        dp[x][y] = Math.max(dp[x][y],dp[x-zero][y-ones]+1);
                    }
                    else
                        break;
                }
            }
        }
        return dp[m][n];
    }
    private int[] counterZerosAndOnes(String str){
        int[] res = new int[2];
        for(int i = 0;i<str.length();i++){
            char c = str.charAt(i);
            if(c=='0')
                res[0]++;
            else
                res[1]++;
        }
        return res;
    }

    public int change(int amount, int[] coins) {

        int[] dp = new int[amount+1];
        dp[0] = 1;

        for(int coin:coins)
        {
            for(int i = 1;i<=amount;i++)
            {
                if(i>=coin)
                    dp[i] = dp[i-coin]+dp[i];
            }
        }

        return dp[amount];
    }

    /**
     * 首先遍历背包后遍历数值可以求解排列总数
     * 首先遍历数值后遍历背包可以求解组合总数
     */
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;

        for(int i = 0;i<nums.length;i++){
            for(int num:nums){
                if(i>=num)
                    dp[i] = dp[i]+dp[i-num];
            }
        }
        return dp[target];
    }

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        for(int i = 1;i<amount+1;i++){
            dp[i] = Integer.MAX_VALUE;
        }

        for(int coin:coins){
            for(int i = 1;i<=amount;i++){
                if(i>=coin&&dp[i-coin]!=Integer.MAX_VALUE){
                    dp[i] = Math.min(dp[i],dp[i-coin]+1);
                }
            }
        }
        return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
    }

    public int numSquares(int n) {
        int dp[] = new int[n+1];

        for(int i = 1;i<n+1;i++){
            dp[i] = Integer.MAX_VALUE;
        }
        for(int i = 1;i<=Math.sqrt(n);i++){
            int num = i*i;
            for(int j = 1;j<=n;j++){
                if(j>num&&dp[j-num]!=Integer.MAX_VALUE){
                    dp[j] = Math.min(dp[j],dp[j-num]+1);
                }
            }
        }
        return dp[n];
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        boolean[] valid = new boolean[s.length() + 1];
        valid[0] = true;

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i && !valid[i]; j++) {
                if (set.contains(s.substring(j, i)) && valid[j]) {
                    valid[i] = true;
                }
            }
        }

        return valid[s.length()];
    }

    public int findLength(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length][nums2.length];
        int res = 0;
        for(int i = 0;i<nums1.length;i++){
            for(int j = 0;j<nums2.length;j++){
                if(nums1[i]==nums2[j])
                {
                    if(i>0&&j>0)
                        dp[i][j] = dp[i-1][j-1]+1;
                    else
                        dp[i][j] = 1;
                }
                res = Math.max(dp[i][j],res);
            }
        }
        return res;
    }

    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length()+1][text2.length()+1];
        int res = 0;
        for(int i = 1;i<=text1.length();i++){
            for(int j = 1;j<=text2.length();j++){
                if(text1.charAt(i-1)==text2.charAt(j-1))
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);

                res = Math.max(res,dp[i][j]);
            }
        }
        return res;
    }

    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int res = 0;
        int[][] dp = new int[nums1.length+1][nums2.length+1];
        for(int i = 1;i<= nums1.length;i++){
            for(int j = 1;j<=nums2.length;j++){
                if(nums1[i-1]==nums2[j-1])
                    dp[i][j] = dp[i-1][j-1]+1;
                else
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                res = Math.max(res,dp[i][j]);
            }
        }
        return res;
    }

    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = nums[0];
        for(int i = 1;i<nums.length;i++){
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
            res = Math.max(res,dp[i]);
        }
        return res;

    }

    public boolean isSubsequence(String s, String t) {
        int[][] dp = new int[s.length()+1][t.length()+1];
        int res = 0;
        for(int i = 1;i<=s.length();i++){
            for(int j = 1;j<=t.length();j++){
                if(s.charAt(i-1)==t.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1]+1;
                else
                    dp[i][j] = dp[i][j-1];
                res = Math.max(res,dp[i][j]);

            }
        }

        return res==s.length()?true:false;
    }

    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length()+1][word2.length()+1];

        for(int i = 1;i<word1.length()+1;i++){
            dp[i][0] = i;
        }
        for(int i = 1;i<word2.length()+1;i++){
            dp[0][i] = i;
        }
        for(int i = 1;i<=word1.length();i++)
        {
            for(int j = 1;j<=word2.length();j++)
            {
                if(word1.charAt(i-1)==word2.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1;
            }
        }
        return dp[word1.length()][word2.length()];
    }

    /**
     * 单调栈法
     * @param prices
     * @return
     */
    public int maxProfitII(int[] prices) {
        int profit = 0;
        LinkedList<Integer> stack = new LinkedList<>();
        for(int i:prices){
            if(stack.isEmpty())
            {
                stack.addLast(i);
                continue;
            }
            if(i<stack.getLast()){
                stack.removeLast();
                stack.addLast(i);
            }else {
                profit = profit+i-stack.getLast();
                stack.removeLast();
                stack.addLast(i);
            }
        }
        return profit;
    }

    public int maxProfitIII(int[] prices){
        int profit = 0;
        return profit;
    }

    /**
     * 并查集
     * @param equations
     * @return
     */
    public boolean equationsPossible(String[] equations) {
        int [] chars = new int[26];
        for(int i = 0;i<26;i++){
            chars[i] = i;
        }

        for(String s:equations){
            if(s.charAt(1)=='='){
                int a = s.charAt(0)-97;
                int b = s.charAt(3)-97;
                chars[findParent(a,chars)] = findParent(b,chars);
            }
        }

        for(String s:equations){
            if(s.charAt(1)=='!'){
                int a = s.charAt(0)-97;
                int b = s.charAt(3)-97;
                if(findParent(a,chars)==findParent(b,chars))
                    return false;
            }
        }

        return true;
    }
    private int findParent(int index,int[] chars){
        while (index!=chars[index]){
            index = chars[index];
        }
        return index;
    }

    /**
     * 博弈：动态规划
     * @param nums
     * @return
     */
    public boolean PredictTheWinner(int[] nums) {
        return stoneGame(nums)>=0;
    }
    private int stoneGame(int[] nums){
        int[][][] dp = new int[nums.length][nums.length][2];
        for(int i = 0;i<nums.length;i++){
            dp[i][i][0]=nums[i];
        }
        for(int i = nums.length-2;i>=0;i--){
            for(int j = i+1;j<nums.length;j++){
                int left = nums[i]+dp[i+1][j][1];
                int right = nums[j]+dp[i][j-1][1];
                if(left>right){
                    dp[i][j][0] = left;
                    dp[i][j][1] = dp[i+1][j][0];
                }else
                {
                    dp[i][j][0] = right;
                    dp[i][j][1] = dp[i][j-1][0];
                }

            }
        }
        return dp[0][nums.length-1][0]-dp[0][nums.length-1][1];
    }

    /**
     * 字符串相乘
     * @param num1
     * @param num2
     * @return
     */
    public String multiply(String num1, String num2) {
        ArrayList<Integer> res = new ArrayList<>();
        ArrayList<Integer> integers = new ArrayList<>();
        for(int i = 0;i<num1.length() + num2.length() + 1;i++){
            res.add(0);
        }
        for(int i = num1.length()-1;i>=0;i--)
        {
            int x = num1.charAt(i) - '0';
            int flag = 0;


            for(int n = i;n<num1.length()-1;n++){
                integers.add(0);
            }

            for(int j = num2.length()-1;j>=0;j--)
            {
                int y = num2.charAt(j) - '0';
                int num = x*y+flag;
                int num_x = num%10;
                flag = num/10;
                integers.add(num_x);
            }

            if(flag!=0)
                integers.add(flag);
            flag = 0;
            int m = 0;

            for(m = 0;m<integers.size();m++){
                int t = integers.get(m)+res.get(m)+flag;
                int t_x = t%10;
                flag = t/10;
                res.set(m,t_x);
            }
            while (flag!=0){
                int t = res.get(m)+flag;
                int t_x = t%10;
                flag = t/10;
                res.set(m,t_x);
                m++;
            }
            integers.clear();
        }
        StringBuilder builder = new StringBuilder();
        boolean isZero = true;
        for(int i = res.size()-1;i>=0;i--){
            if(isZero&&res.get(i)!=0)
                isZero = false;
            if(!isZero)
                builder.append(res.get(i));
        }
        return builder.toString();
    }

    public String minNumber(int[] nums){

        return null;
    }

    /**
     * 最小覆盖子串，滑动窗口
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> charMap = new HashMap<>();
        HashMap<Character, Integer> windows = new HashMap<>();

        for(int i = 0;i<t.length();i++){
            charMap.put(t.charAt(i),charMap.getOrDefault(t.charAt(i),0)+1);
        }
        int viald = 0;
        int windowR = 0;
        int windowL = 0;
        int start = 0;
        int minLength = Integer.MAX_VALUE;

        while (windowR<s.length()) {
            char Schar = s.charAt(windowR);
            windowR++;
            if(charMap.containsKey(Schar)){
                windows.put(Schar,windows.getOrDefault(Schar,0)+1);
                if(windows.get(Schar).equals(charMap.get(Schar)))
                    viald++;
            }

            while (viald==charMap.size())
            {
                if(windowR - windowL < minLength){
                    minLength = windowR - windowL;
                    start = windowL;
                }
                char Tchar = s.charAt(windowL);
                if(charMap.containsKey(Tchar)){
                    if(windows.get(Tchar).equals(charMap.get(Tchar)))
                        viald--;
                    windows.put(Tchar,windows.get(Tchar)-1);
                }
                windowL++;
            }

        }
        return minLength==Integer.MAX_VALUE?"":s.substring(start,start+minLength);
    }

    /**
     * 轮转数组,不使用额外空间的方法是先整体翻转数组后各自翻转部分
     * @param nums
     * @param k
     */
    public void rotate(int[] nums,int k){
        k = k%nums.length;
        int[] copyNums = new int[nums.length];
        int cutPoint = nums.length - k;
        int index = 0;
        for(int i = cutPoint;i<nums.length;i++){
            copyNums[index] = nums[i];
            index++;
        }
        for(int i = 0;i<cutPoint;i++){
            copyNums[index] = nums[i];
            index++;
        }
        for(int i = 0;i<nums.length;i++)
            nums[i] = copyNums[i];
    }

    public Node copyRandomList(Node head) {
        Node temp = head;
        Node maphead = head;
        HashMap<Node, Node> nodeHashMap = new HashMap<>();
        while (temp!=null){
            Node node = new Node(temp.val);
            nodeHashMap.put(temp,node);
            temp = temp.next;
        }
        nodeHashMap.put(null,null);
        while (head!=null){
            nodeHashMap.get(head).next = nodeHashMap.get(head.next);
            nodeHashMap.get(head).random = nodeHashMap.get(head.random);
        }
        return nodeHashMap.get(maphead);
    }
    public int findRandomIndex(Node head, Node random){
        int index = 0;
        Node tempHead = head;
        while (tempHead!=random){
            tempHead = tempHead.next;
            index++;
        }
        return index;
    }

    public int kthSmallest(TreeNode root, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        findKTreeVal(root,list,k);
        return list.get(k-1);

    }
    private void findKTreeVal(TreeNode node,List<Integer> list,int k){
        if(list.size()==k||node==null)
            return;
        findKTreeVal(node.left,list,k);
        list.add(node.val);
        findKTreeVal(node.right,list,k);
    }

    public List<Integer> rightSideView(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        ArrayList<Integer> res = new ArrayList<>();
        if(root!=null)
            queue.addLast(root);
        while (!queue.isEmpty())
        {
            int size = queue.size();
            res.add(queue.getLast().val);
            for(int i = size;i>=0;i--){
                TreeNode node = queue.removeFirst();
                if(node.left!=null)
                    queue.addLast(node.left);
                if(node.right!=null)
                    queue.addLast(node.right);
            }
        }
        return res;
    }

    public int pathSum(TreeNode root, int targetSum) {
        int[] res = new int[1];
        ArrayList<Integer> list = new ArrayList<>();
        findWay(root,targetSum,list,res);
        return res[0];
    }
    private int NumTartgetSum(ArrayList<Integer> list,int target){
        int counter = 0;
        long sum = 0;
        for(int i = list.size()-1;i>=0;i--){
            sum = sum+list.get(i);
            if(sum == target)
                counter++;
        }
        return counter;
    }
    private void findWay(TreeNode node,int targetNum,ArrayList<Integer> list,int[] res){
        if(node==null)
            return;
        list.add(node.val);
        findWay(node.left,targetNum,list,res);
        findWay(node.right,targetNum,list,res);

        int conter = NumTartgetSum(list, targetNum);
        res[0] = res[0]+conter;

        list.remove(list.size()-1);
    }

    public int findDuplicate(int[] nums) {
        for(int i = 0;i<nums.length;i++){
            int num = nums[i];
            if(num<0)
                num = -num;
            if(nums[num-1]<0)
                return num;
            else
                nums[num-1] = -nums[num-1];
        }
       return 0;
    }

    public List<Integer> partitionLabels(String s) {
        HashMap<Character, int[][]> map = new HashMap<>();

        for(int i = 0;i<s.length();i++){
            updateMap(s.charAt(i),map,i);
        }
        Set<Character> keySet = map.keySet();
        int[][] arrays = new int[keySet.size()][2];
        int counter = 0;
        for(char c:keySet){
            arrays[counter][0] = map.get(c)[0][0];
            arrays[counter][1] = map.get(c)[0][1];
            counter++;
        }
        int[][] merges = merge(arrays);
        List<Integer> list = new ArrayList<>();
        for(int[] merge:merges){
            int length = merge[1] - merge[0] + 1;
            list.add(length);
        }

        return list;
    }
    private void updateMap(char c,HashMap<Character,int[][]> map,int index){
        if(!map.containsKey(c)){
            int[][] indexs = new int[][]{{index,index}};
            map.put(c,indexs);
        }else {
            map.get(c)[0][1] = index;
        }
    }
    private int[][] merge(int[][] intervals) {

        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        LinkedList<int[]> list = new LinkedList<>();
        for(int[] nums:intervals)
        {
            if(list.isEmpty())
                list.addLast(nums);
            else
            {
                int[] temp = list.getLast();
                if(nums[0]>temp[1]){
                    list.addLast(nums);
                }else {
                    int right = nums[1]>temp[1]?nums[1]:temp[1];
                    int [] newMerge = new int[]{temp[0],right};
                    list.removeLast();
                    list.addLast(newMerge);
                }
            }
        }

        int [][] res = new int[list.size()][2];
        int index = 0;
        for(int[] nums:list)
        {
            res[index] = nums;
            index++;
        }
        return res;

    }

    public int maxVowels(String s, int k) {
        HashSet<Character> set = new HashSet<>();
        set.add('a');
        set.add('e');
        set.add('i');
        set.add('o');
        set.add('u');

        int left = 0;
        int right = 0;
        int counter = 0;
        int maxRes = 0;

        while (right<s.length())
        {
            if(right-left<k){
                if(set.contains(s.charAt(right)))
                    counter++;
            }
            else
            {
                if(set.contains(s.charAt(right)))
                    counter++;
                if(set.contains(s.charAt(left)))
                    counter--;
                left++;
            }
            right++;
            if(counter>maxRes)
                maxRes = counter;
        }
        return maxRes;
    }

    public int longestSubarray(int[] nums) {
        int[] ZerosAndOnesCounter = new int[2];
        int right = 0;
        int left = 0;
        int res = 0;
        boolean hasZero = false;

        while (right<nums.length){
            ZerosAndOnesCounter[nums[right]]++;
            while (ZerosAndOnesCounter[0]==2){
                hasZero = true;
                if(res<ZerosAndOnesCounter[1])
                    res = ZerosAndOnesCounter[1];
                ZerosAndOnesCounter[nums[left]]--;
                left++;
            }
            right++;
        }
        if(res<ZerosAndOnesCounter[1])
            res =ZerosAndOnesCounter[1];
        if(hasZero)
            return res;
        else {
            if(ZerosAndOnesCounter[0]==0)
                return ZerosAndOnesCounter[1]-1;
            else
                return ZerosAndOnesCounter[1];
        }

    }

    public double findMaxAverage(int[] nums, int k) {
        int left = 0;
        int right = 0;
        double sum = 0;
        double maxAvg = -Double.MAX_VALUE;
        boolean isMatch = true;

        while (right<nums.length){
            if(isMatch&&right-left<k)
            {
                sum = sum+nums[right];
            }
            else
            {
                isMatch = false;
                if(sum/k>maxAvg)
                    maxAvg = sum/k;
                sum = sum - nums[left]+nums[right];
                left++;
            }
            right++;
        }
        return sum/k<maxAvg?maxAvg:sum/k;

    }

    public boolean increasingTriplet(int[] nums) {

        return true;

    }

    public int maxEnvelopes(int[][] envelopes) {
        int maxCount = 0;
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0]!=0?o1[0] - o2[0]:o1[1] - o2[1];
            }
        });
        int[] dp = new int[envelopes.length];

        for(int i = 1;i<dp.length;i++){
            int[] nowEnv = envelopes[i];
            for(int j = i-1;j>=0;j--){
                if(envelopes[j][0]<nowEnv[0]&&envelopes[j][1]<nowEnv[1])
                    dp[i] = Math.max(dp[i],dp[j]+1);
            }
            maxCount = Math.max(dp[i],maxCount);
        }
        return maxCount;

    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        LinkedList<TreeNode> Ppath = new LinkedList<>();
        LinkedList<TreeNode> Qpath = new LinkedList<>();
        dfs(root,p,Ppath);
        dfs(root,q,Qpath);

        for(TreeNode nodep:Ppath){
            for(TreeNode nodeq:Qpath){
                if(nodep==nodeq)
                    return nodep;
            }
        }

        return null;
    }
    private void dfs(TreeNode root,TreeNode p,LinkedList<TreeNode> path){
        if(root==null||path.peek()==p)
            return;
        if(root==p&&path.peek()!=p){
            path.addFirst(p);
            return;
        }
        path.addFirst(root);

        dfs(root.left,p,path);
        dfs(root.right,p,path);
        if(path.peek()!=p)
            path.removeFirst();

    }

    public int longestOnes(int[] nums, int k) {
        int[] res = new int[1];
        dfs(nums,k,0,0,res);
        //System.out.println(res[0]);
        return res[0];

    }
    private void dfs(int[] nums,int k,int count,int index,int[] res){
        if(index==nums.length){
            if(count>res[0])
                res[0] = count;
            return;
        }

        if(nums[index]==0){
            if(k==0){
                if(count>res[0])
                    res[0] = count;
                dfs(nums,k,0,index+1,res);
            }else {
                if(count>res[0])
                    res[0] = count;
                dfs(nums,k,0,index+1,res);
                dfs(nums,k-1,count+1,index+1,res);
            }
        }else
            dfs(nums,k,count+1,index+1,res);
    }

    public int longestOnesII(int[] nums, int k){
        int right = 0;
        int left = 0;
        int count = 0;
        int res = 0;

        while (right<nums.length){
            if(nums[right]==1){
                count = right-left+1;
                right++;
                if(count>res)
                    res = count;
            }else {
                if(k>0){
                    count = right-left+1;
                    k--;
                    right++;
                    if(count>res)
                        res = count;
                }else {
                    while (k==0&&right>=left){
                        if(left<right&&nums[left]==0){
                            k++;
                        }
                        left++;
                    }
                    count = right-left+1;
                    if(k>0)
                        k--;
                    right++;
                    if(count>res)
                        res = count;
                }
            }
        }
        return res;
    }

    public int findMaxConsecutiveOnes(int[] nums) {
        int count = 0;
        int res = 0;
        for(int i = 0;i<nums.length;i++){
            if(nums[i]==1){
                count++;
                if(res<count)
                    res = count;
            }else {
                if(res<count){
                    res = count;
                }
                count = 0;
            }
        }
        return res;
    }

    public void reorderList(ListNode head) {
        HashMap<Integer, ListNode> map = new HashMap<>();
        int index = 1;
        while (head!=null){
            map.put(index,head);
            index++;
            head = head.next;
            map.get(index).next=null;
        }

        int size = map.size();
        int n = size+1;

        ListNode node = new ListNode(0, null);
        ListNode res = node;
        index  = 1;


        while (index<=size/2){
            node.next = map.get(index);
            node = node.next;
            node.next = map.get(n-index);
            node = node.next;
            index++;
        }
        if(size%2!=0)
            node.next = map.get(index);

        head = res.next;

    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        return dfs(p,q);
    }
    private boolean dfs(TreeNode p,TreeNode q){
        if(p==null&&q==null)
            return true;
        if((p==null&&q!=null)||(p!=null&&q==null)||(p.val!=q.val))
            return false;
        return dfs(p.left,q.left)&&dfs(p.right,q.right);
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> temp = new LinkedList<>();
        boolean[] visited = new boolean[nums.length];
        DfsSubsetsWithDup(nums,0,visited,res,temp);

        return res;
    }
    private void DfsSubsetsWithDup(int[] nums,int index,boolean[] visited,List<List<Integer>> res,LinkedList<Integer> temp){
        res.add(new LinkedList<>(temp));

        for(int i = index;i<nums.length;i++){
            if(visited[i]||(i>0&&nums[i]==nums[i-1]&&!visited[i-1]))
                continue;

            visited[i] = true;
            temp.addLast(nums[i]);
            DfsSubsetsWithDup(nums,i+1,visited,res,temp);

            visited[i] = false;
            temp.removeLast();
        }
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] visited = new boolean[nums.length];
        List<List<Integer>> res = new LinkedList<>();
        LinkedList<Integer> temp = new LinkedList<>();
        Arrays.sort(nums);
        DfsPermuteUnique(nums,visited,res,temp);
        return res;
    }
    private void DfsPermuteUnique(int[] nums,boolean[] visited,List<List<Integer>> res,LinkedList<Integer> temp){
        if(temp.size()==nums.length){
            res.add(new LinkedList<>(temp));
            return;
        }
        for(int i = 0;i<nums.length;i++){
            if((i>0&&nums[i]==nums[i-1]&&!visited[i-1])||visited[i]){
                continue;
            }
            if(!visited[i]){
                visited[i] = true;
                temp.addLast(nums[i]);
                DfsPermuteUnique(nums,visited,res,temp);
            }
            visited[i] = false;
            temp.removeLast();
        }
    }

    public Stack<Integer> StackSort(Stack<Integer> stack){
        Stack<Integer> help = new Stack<>();
        int count = 0;

        while (!stack.isEmpty()){
            int num = stack.pop();

            if(help.isEmpty()){
                help.push(num);
                continue;
            }

            while (!help.isEmpty()&&help.peek()>num){
                stack.push(help.pop());
                count++;
            }

            help.push(num);

            while (count>0){
                help.push(stack.pop());
                count--;
            }
        }
        return help;
    }

    public int OneZeroPackageSolution(int cap,int[] weights,int[] values){
        int[] dp = new int[cap+1];

        for(int i = 0;i<weights.length;i++){
            int weight = weights[i];
            int value = values[i];

            for(int j = dp.length-1;j>=weight;j--){
                dp[j] = Math.max(dp[j],dp[j-weight]+value);
            }

        }

        return dp[cap];
    }

    public void recoverTree(TreeNode root) {
        ArrayList<TreeNode> list = new ArrayList<>();
        bfs(root,list);

        TreeNode[] nodes = new TreeNode[2];

        for(int i = 1;i<list.size();i++){
            if(list.get(i).val<list.get(i-1).val){
                nodes[0] = list.get(i-1);
                break;
            }
        }
        if(nodes[0]==null)
            return;

        for(int i = 0;i<list.size()-1;i++){
            if(list.get(i).val>list.get(i+1).val){
                nodes[1] = list.get(i+1);
            }
        }

        int temp = nodes[0].val;
        nodes[0].val = nodes[1].val;
        nodes[1].val = temp;


    }
    private void bfs(TreeNode root,ArrayList<TreeNode> list){
        if(root==null)
            return;
        bfs(root.left,list);
        list.add(root);
        bfs(root.right,list);
    }

    public int minNumberDisappeared(int[] nums){
        int size = nums.length;
        int[] postive = new int[size];

        for(int i = 0;i<size;i++){
            if(nums[i]>0&&nums[i]-1<size){
                postive[nums[i]-1] = -1;
            }
        }

        for(int i = 0;i<size;i++){
            if(postive[i]==0)
                return i+1;
        }

        return size+1;
    }

    public TreeNode sortedListToBST(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        while (head!=null){
            list.add(head.val);
            head = head.next;
        }
        int[] nums = new int[list.size()];
        for(int i = 0;i<nums.length;i++){
            nums[i] = list.get(i);
        }

        return doArrayToBST(nums,0,nums.length-1);
    }

    public TreeNode sortedArrayToBST(int[] nums){
        return doArrayToBST(nums,0,nums.length-1);
    }
    private TreeNode doArrayToBST(int[] nums,int left,int right){
        if(left>right)
            return null;
        int mid = (left+right)/2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = doArrayToBST(nums,left,mid-1);
        node.right = doArrayToBST(nums,mid+1,right);
        return node;
    }

    public void showBTS(TreeNode root){
        if(root==null)
            return;
        showBTS(root.left);
        System.out.print(root.val+" ");
        showBTS(root.right);
    }
    public ListNode insertionSortList(ListNode head) {

        ListNode resHead = null;
        ListNode resLast = null;

        while (head!=null){

            if(resHead==null){
                resHead = new ListNode(head.val);
                resLast = resHead;
                head = head.next;
                continue;
            }

            if(head.val>=resLast.val){
                resLast.next = new ListNode(head.val);
                resLast = resLast.next;
                head = head.next;
                continue;
            }

            if(head.val<=resHead.val){
                ListNode newHead = new ListNode(head.val);
                newHead.next = resHead;
                resHead = newHead;
                head = head.next;
                continue;
            }

            ListNode current = resHead;

            while (current.next!=null){
                if(current.next.val>=head.val){
                    ListNode temp = current.next;
                    current.next = new ListNode(head.val);
                    current.next.next = temp;
                    head = head.next;
                    break;
                }
                current = current.next;
            }

        }
        return resHead;
    }

    public int singleNumber(int[] nums) {
        int[] binary = new int[32];
        int minIntegerCount = 0;

        for(int num:nums){
            if(num==Integer.MIN_VALUE){
                minIntegerCount++;
                continue;
            }
            if(num<0){
                num = -num;
                binary[0]++;
            }
            String binaryString = Integer.toBinaryString(num);
            int index = 31;
            for(int i = binaryString.length()-1;i>=0;i--){
                if(binaryString.charAt(i)=='1'){
                    binary[index]++;
                }
                index--;
            }
        }

        int sum = 0;
        int ans = 1;
        for(int i = binary.length-1;i>=1;i--){
            if(binary[i]%3!=0){
                sum = sum+ans;
            }
            ans = ans*2;
        }
        if(minIntegerCount==1)
            return Integer.MIN_VALUE;
        return binary[0]%3!=0?-sum:sum;
    }

    public ListNode partition(ListNode head, int x) {

        ListNode newhead = new ListNode();
        newhead.next = head;
        head = newhead;
        ListNode flagNode = head;
        ListNode firstNode = null;

        while (flagNode!=null){
            if(flagNode.next!=null&&flagNode.next.val>=x){
                firstNode = flagNode;
                break;
            }
            flagNode = flagNode.next;

        }

        while (firstNode!=null){
            if(firstNode.next!=null&&firstNode.next.val<x){
                ListNode temp = firstNode.next;
                firstNode.next = temp.next;
                temp.next = flagNode.next;
                flagNode.next = temp;
                flagNode = temp;
                continue;
            }
            firstNode = firstNode.next;
        }

        return head.next;
    }

    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n+1];
        if(s.charAt(0)=='0')
            return 0;
        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2;i<=n;i++){
            int index = i-1;
            if(s.charAt(index)!='0'){
                if(s.charAt(index-1)!='0'&&Integer.valueOf(s.substring(index-1,index+1))<=26){
                    dp[i] = dp[i-1]+dp[i-2];
                }else {
                    dp[i] = dp[i-1];
                }
            }else {
                if(s.charAt(index-1)=='0'||Integer.valueOf(s.substring(index-1,index+1))>26)
                    return 0;
                dp[i] = dp[i-2];
            }
        }
        return dp[n];
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if(root==null){
            return res;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        int size = 0;
        boolean flag = true;

        while (!queue.isEmpty()){
            size = queue.size();
            LinkedList<Integer> temp = new LinkedList<>();
            LinkedList<TreeNode> tempQueue = new LinkedList<TreeNode>();
            while (size>0){
                TreeNode node = queue.pollFirst();
                size--;
                temp.add(node.val);
                if(!flag){
                    if(node.right!=null)
                        tempQueue.addFirst(node.right);
                    if(node.left!=null)
                        tempQueue.addFirst(node.left);
                }else {
                    if(node.left!=null)
                        tempQueue.addFirst(node.left);
                    if(node.right!=null)
                        tempQueue.addFirst(node.right);
                }
            }
            queue = tempQueue;
            res.add(temp);
            flag = !flag;
        }
        return res;
    }

    //优化解，爬坡法
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        if(n==1||nums[0]>nums[1])
            return 0;
        if(nums[n-1]>nums[n-2])
            return n-1;

        int index = 1;
        while (index<=n-2){
            if(nums[index]>nums[index+1])
                return index;
            index++;
        }
        return -1;
    }
    public int findPeakElementII(int[] nums) {
        if(nums.length==1)
            return nums[0];
        int[] res = new int[]{-1};
        doFindPeakElement(0,nums.length-1,nums,res);
        return res[0];
    }
    private void doFindPeakElement(int left,int right,int[] nums,int[] res){
        if(left<right)
            return;

        int index = (left+right)/2;
        int num = nums[index];

        if(isPeak(index,nums)){
            res[0] = index;
            return;
        }

        if(res[0]==-1&&num<nums[index+1])
            doFindPeakElement(index+1,right,nums,res);
        if(res[0]==-1&&num<nums[index-1])
            doFindPeakElement(left,index-1,nums,res);
    }
    private boolean isPeak(int index,int[] nums){
        if(index==0||index==nums.length-1) {
            if (index == 0 && nums[index] > nums[index + 1])
                return true;
            if (index == nums.length - 1 && nums[index] > nums[index - 1])
                return true;
        }else {
            if (nums[index] > nums[index - 1] && nums[index] > nums[index + 1])
                return true;
        }
        return false;
    }

    //java split（）使用“.” “\” "|" "*" "+"来分割时，需要转义
    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");

        int indexv1 = 0;
        int indexv2 = 0;

        while (indexv2<=v2.length-1&&indexv1<=v1.length-1){
            String t1 = v1[indexv1];
            Integer n1 = Integer.valueOf(t1);

            String t2 = v2[indexv2];
            Integer n2 = Integer.valueOf(t2);

            if(n2>n1)
                return -1;
            if(n2<n1)
                return 1;

            indexv2++;
            indexv1++;

        }

        while (indexv1<v1.length){
            String t1 = v1[indexv1];
            Integer n1 = Integer.valueOf(t1);

            if(n1>0)
                return 1;
            indexv1++;
        }
        while (indexv2<v2.length){
            String t2 = v2[indexv2];
            Integer n2 = Integer.valueOf(t2);

            if(n2>0)
                return -1;
            indexv2++;
        }
        return 0;
    }

    public String largestNumber(int[] nums) {
        String[] strings = new String[nums.length];

        for(int i = 0;i<strings.length;i++)
            strings[i] = String.valueOf(nums[i]);

        Arrays.sort(strings, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return compareTwoStringNum(s1,s2);
            }

        });
        StringBuilder stringBuilder = new StringBuilder();
        for(String s:strings){
            stringBuilder.append(s);
        }
        while (stringBuilder.length()>0&&stringBuilder.charAt(0)=='0')
            stringBuilder.delete(0,1);
        if(stringBuilder.length()==0)
            return "0";
        return stringBuilder.toString();
    }
    private int compareTwoStringNum(String s1,String s2){
        if(s1.length()==s2.length()){
            return Integer.valueOf(s2) - Integer.valueOf(s1);
        }
        long n1 = Long.valueOf(s1+s2);
        long n2 = Long.valueOf(s2+s1);
        if(n1>n2)
            return -1;
        if(n2>n1)
            return 1;
        return 0;
    }

    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        int left = 0;
        int right = numbers.length-1;

        int sum = 0;

        while (left<right){
            sum = numbers[left]+numbers[right];
            if(sum==target)
                break;
            if(sum> target)
                right--;
            if(sum<target)
                left++;
        }
        res[0] = left+1;
        res[1] = right+1;
        return res;
    }

    public List<List<Integer>> pathSumII(TreeNode root, int targetSum) {
        List<List<Integer>> res = new LinkedList<>();
        LinkedList<Integer> temp = new LinkedList<>();
        doPathSumII(root,targetSum,0,temp,res);
        return res;
    }
    private void doPathSumII(TreeNode node,int targetSum,int sum,LinkedList<Integer> temp,List<List<Integer>> res){

        if(node==null)
            return;
        if(sum+node.val==targetSum&&isLastNode(node)){
            temp.addLast(node.val);
            res.add(new LinkedList<>(temp));
            temp.removeLast();
            return;
        }

        temp.addLast(node.val);
        doPathSumII(node.left,targetSum,sum+node.val,temp,res);
        doPathSumII(node.right,targetSum,sum+node.val,temp,res);
        temp.removeLast();
    }
    private boolean isLastNode(TreeNode node){
        if(node.right==null&node.left==null)
            return true;
        return false;
    }

    public List<String> findRepeatedDnaSequences(String s) {
        LinkedList<String> list = new LinkedList<>();
        StringBuilder stringBuilder = new StringBuilder();
        HashMap<String, Integer> map = new HashMap<>();

        for(int i = 0;i<s.length();i++){
            char c = s.charAt(i);
            if(stringBuilder.length()<10)
                stringBuilder.append(c);
            else {
                String string = stringBuilder.toString();
                map.put(string,map.getOrDefault(string,0)+1);
                stringBuilder.deleteCharAt(0).append(c);
            }
        }

        String string = stringBuilder.toString();
        map.put(string,map.getOrDefault(string,0)+1);

        Set<String> strings = map.keySet();

        for(String key:strings){
            if(map.get(key)>1)
                list.add(key);
        }
        return list;
    }

    public int sumNumbers(TreeNode root) {
        int[] res = new int[1];
        doSumNumbers(root,0,res);
        return res[0];
    }
    private void doSumNumbers(TreeNode root,int sum,int[] res){
        if(root.right==null&&root.left==null){
            res[0] = res[0]+sum+root.val;
            return;
        }
        if(root.left!=null)
            doSumNumbers(root.left,(sum+root.val)*10,res);
        if(root.right!=null)
            doSumNumbers(root.right,(sum+root.val)*10,res);
    }

    /**
     * 摩尔投票法
     * @param nums
     * @param n
     * @return
     */
    public List<Integer> majorityElement(int[] nums,int n) {
        List<Integer> res = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        ArrayDeque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < nums.length; i++) {
            if(map.size()<n-1){
                map.put(nums[i],map.getOrDefault(nums[i],0)+1);
                continue;
            }

            if(map.size()==n-1){
                if(map.containsKey(nums[i])){
                    map.put(nums[i],map.get(nums[i])+1);
                }else {
                    Set<Integer> keySet = map.keySet();

                    for (Integer key : keySet) {
                        if(map.get(key)-1<=0)
                            deque.addFirst(key);
                        else
                            map.put(key,map.get(key)-1);
                    }

                    if(deque.size()==n-1){
                        map.clear();
                        deque.clear();
                    }else {
                        while (!deque.isEmpty()){
                            Integer pop = deque.pop();
                            map.remove(pop);
                        }
                    }
                }
            }
        }

        for (Integer key : map.keySet()) {
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                if(nums[i]==key)
                    count++;
            }
            if(count>(nums.length/n))
                res.add(key);
        }

        return res;
    }

    public List<List<Integer>> combinationSumIII(int k, int n) {
        List<List<Integer>> res = new LinkedList<>();
        LinkedList<Integer> temp = new LinkedList<>();
        doCombinationSumIII(k,0,0,n,temp,res);
        return res;
    }

    private void doCombinationSumIII(int k,int sum,int num,int target,LinkedList<Integer> temp,List<List<Integer>> res){
        if(temp.size()==k){
            if(sum==target){
                res.add(new LinkedList<>(temp));
            }
            return;
        }

        for(int i = num+1;i<=9;i++){
            if(temp.size()<k){
                if(sum+i>target)
                    break;
                else {
                    temp.addLast(i);
                    doCombinationSumIII(k,sum+i,i,target,temp,res);
                    temp.removeLast();
                }
            }
        }
    }

    public int hIndex(int[] citations) {
        int n = citations.length;
        Arrays.sort(citations);
        int max = 0;

        for(int i = 0;i<n;i++){
            if(citations[i]>=n-i){
                max = Math.max(max,n-i);
                break;
            }
        }
        return max;
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length-k+1];
        LinkedList<Integer> queue = new LinkedList<>();
        int resIndex = 0;

        for(int i = 0;i<nums.length;i++){

            if(queue.isEmpty())
                queue.addLast(i);
            else {
                if(i-queue.getFirst()==k)
                    queue.removeFirst();

                int num = nums[i];

                while (!queue.isEmpty()&&num>=nums[queue.getLast()]){
                    queue.removeLast();
                }

                queue.addLast(i);
            }

            if(i>=k-1) {
                res[resIndex] = nums[queue.getFirst()];
                resIndex++;
            }

        }
        return res;
    }

    /**
     * O(n)超时
     * @param n
     * @return
     */
    public int countDigitOne(int n) {
        if(n==0)
            return 0;
        if(n<=9)
            return 1;
        int[] dp = new int[1000];
        dp[1] = 1;

        int count = 1;

        for(int i=10;i<=n;i++){
            if(i<dp.length){
                dp[i] = dp[i/10]+dp[i%10];
                count = count+dp[i];
            }
            else {
                count = count+countDigitOneBig(dp,i);
            }

        }
        return count;
    }
    private int countDigitOneBig(int[] nums,int num){
        if(num<nums.length)
            return nums[num];
        return countDigitOneBig(nums,num/1000)+countDigitOneBig(nums,num%1000);
    }
    /**
     * 队列记录前序节点
     * @param head
     * @return
     */
    public ListNode removeNodes(ListNode head) {
        if(head==null||head.next==null)
            return head;

        ListNode first = new ListNode(Integer.MAX_VALUE);
        first.next = head;
        ListNode next = head;

        LinkedList<ListNode> queue = new LinkedList<>();

        while (next!=null){
            if(first.val>=next.val){
                queue.addFirst(first);
                first = first.next;
                next = next.next;
            }else {
                ListNode temp = queue.removeFirst();
                temp.next = next;
                first.next = null;
                first = temp;
            }
        }
        return queue.getLast().next;
    }

    /**
     * 交换链表节点值删除节点
     * @param node
     */
    public void deleteNode(ListNode node) {
        ListNode pre = node;
        ListNode next = pre.next;

        while (next.next!=null){
            swapListNode(pre,next);
            pre = pre.next;
            next = next.next;
        }
        swapListNode(pre,next);
        pre.next = null;

    }
    private void swapListNode(ListNode node1,ListNode node2){
        int temp = node1.val;
        node1.val = node2.val;
        node2.val = temp;
    }
    public String getHint(String secret, String guess) {

        int[] map = new int[10];
        int B = 0;
        int A = 0;
        for (int i = 0; i < secret.length(); i++) {
            int index = (int)secret.charAt(i)-48;
            map[index]++;
        }


        for (int i = 0; i < guess.length(); i++) {
            int sc = (int)secret.charAt(i)-48;
            int gc = (int)guess.charAt(i)-48;

            if(sc==gc){
                if(map[gc]==0) B--;
                else map[gc]--;
                A++;
            }else {
                if(map[gc]>0){
                    map[gc]--;
                    B++;
                }
            }
        }

        return A+"A"+B+"B";

    }
    /**
     * 需要使用不知名算法
     * @param matrix
     * @param numSelect
     * @return
     */
    public int maximumRows(int[][] matrix, int numSelect) {
        Integer[][] count = new Integer[matrix[0].length][2];
        int res = 0;

        for(int i = 0;i<matrix[0].length;i++){
            count[i][0] = i;
            count[i][1] = 0;
            for(int j = 0;j<matrix.length;j++){
                if(matrix[j][i]==1) count[i][1]++;
            }
        }

        Arrays.sort(count, new Comparator<Integer[]>() {
            @Override
            public int compare(Integer[] o1, Integer[] o2) {
                return o2[1] - o1[1];
            }
        });

        showArray(count);

        HashSet<Integer> set = new HashSet<Integer>(numSelect);
        for (int i = 0; i < numSelect; i++) {
            set.add(count[i][0]);
        }

        boolean isMatch;

        for (int i = 0; i < matrix.length; i++) {
            isMatch = true;
            for (int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j]==1&&!set.contains(j)){
                    isMatch = false;
                    break;
                }
            }
            if(isMatch)
                res++;
        }

        return res;
    }

    public String removeDuplicateLettersByBadWay(String s) {

        HashMap<Character, Integer> map = new HashMap<>();
        for(int i = 0;i<s.length();i++){
            char c = s.charAt(i);
            map.put(c,map.getOrDefault(c,0)+1);
        }

        boolean[] isDelete = new boolean[s.length()];

        for(int i = 0;i<s.length();i++){
            char c = s.charAt(i);

            if(map.get(c)>1&&havaSame(c,s,i-1,isDelete)){
                map.put(c,map.get(c)-1);
                isDelete[i] = true;
                continue;
            }

            for(int j = i-1;j>=0;j--){
                char cmp = s.charAt(j);

                if(map.get(cmp)==1&&!isDelete[j]){
                    if(havaSame(c,s,j,isDelete)) {
                        isDelete[i] = true;
                        map.put(c, map.get(c) - 1);
                    }
                    break;
                }

                if(map.get(cmp)>1&&cmp>c&&!isDelete[j]){
                    isDelete[j] = true;
                    map.put(cmp,map.get(cmp)-1);
                }else {
                    if(cmp==c&&!isDelete[j]){
                        isDelete[i] = true;
                        map.put(cmp,map.get(cmp)-1);
                    }
                }
            }


        }

        StringBuilder builder = new StringBuilder();

        for(int i = 0;i<s.length();i++){
            if(!isDelete[i])
                builder.append(s.charAt(i));
        }


        return builder.toString();
    }
    private boolean havaSame(char target,String s,int start,boolean[] isDelete){
        for(int i = start;i>=0;i--){
            if(target==s.charAt(i)&&!isDelete[i])
                return true;
        }
        return false;
    }
    public String removeDuplicateLetters(String s){
        HashMap<Character, Integer> map = new HashMap<>();
        for(int i = 0;i<s.length();i++){
            char c = s.charAt(i);
            map.put(c,map.getOrDefault(c,0)+1);
        }

        LinkedList<Character> queue = new LinkedList<>();
        HashSet<Character> set = new HashSet<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if(set.contains(c)){
                map.put(c,map.get(c)-1);
                continue;
            }

            set.add(c);

            while (!queue.isEmpty()&&queue.getLast()>c&&map.get(queue.getLast())>1){
                    Character removed = queue.removeLast();
                    map.put(removed,map.get(removed)-1);
                    set.remove(removed);
            }
            queue.addLast(c);

        }

        StringBuilder builder = new StringBuilder();
        for(char c:queue)
            builder.append(c);
        return builder.toString();
    }
    /**
     * 移掉K位数
     * @param num
     * @param k
     * @return
     */
    public String removeKdigits(String num, int k) {
        if(k==num.length())
            return "0";
        LinkedList<Character> queue = new LinkedList<>();

        for (int i = 0; i < num.length(); i++) {
            char c = num.charAt(i);
            while (!queue.isEmpty()&&k>0&&c<queue.getLast()){
                    queue.removeLast();
                    k--;
            }
            queue.addLast(c);
        }

        while (!queue.isEmpty()&&k>0){
            queue.removeLast();
            k--;
        }
        while (!queue.isEmpty()&&queue.getFirst()=='0')
            queue.removeFirst();

        StringBuilder builder = new StringBuilder();

        for(Character s:queue)
            builder.append(s);
        return builder.toString().equals("")?builder.toString():"0";
    }

    public List<String> generateParenthesis(int n) {
        LinkedList<String> res = new LinkedList<>();
        doGenerateParenthesis(n,0,0,"",res);
        return res;
    }
    private void doGenerateParenthesis(int n,int left,int right,String s,List<String> res){
        if(s.length()==n*2){
            res.add(s);
            return;
        }
        if(left<n) {
            if (left > right) {
                doGenerateParenthesis(n, left + 1, right, s + "(", res);
                doGenerateParenthesis(n, left, right + 1, s + ")", res);
            } else
                doGenerateParenthesis(n, left + 1, right, s + "(", res);
        }
        else
            doGenerateParenthesis(n, left, right + 1, s + ")", res);
    }


    /*
    递归超时
     */
    public boolean stoneGameII(int[] piles){
        return doGame(0,piles.length-1,0,0,true,piles);
    }
    private boolean doGame(int left,int right,int sumA,int sumB,boolean isA,int[] piles){
        if(left > right)
            return sumA > sumB;

        if(isA){
            return doGame(left+1,right,sumA+piles[left],sumB,!isA,piles)
                    || doGame(left,right-1,sumA+piles[right],sumB,!isA,piles);
        }else {
            return doGame(left+1,right,sumA,sumB+piles[left],!isA,piles)
                    || doGame(left,right-1,sumA,sumB+piles[right],!isA,piles);
        }
    }

    public boolean stoneGameBetter(int[] piles) {
        int length = piles.length;
        int[][] dp = new int[length][length];
        for (int i = 0; i < length; i++) {
            dp[i][i] = piles[i];
        }
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }
        return dp[0][length - 1] > 0;
    }

    public void rotateII(int[] nums, int k) {
        if(nums.length == 1||nums.length==0)
            return;

        int count = 0;
        int n = nums.length;

        for(int start = 0;start < n;start++){
            int now = start;
            int tempVal = nums[now];
            while (true){
                int exchange = (now+k)%n;
                int temp = nums[exchange];
                nums[exchange] = tempVal;
                tempVal = temp;
                count++;

                if(exchange == start)
                    break;

                now = exchange;
            }

            if(count == n)
                break;
        }
    }

    public void rotate(int[][] matrix){
        int n = matrix.length;

        for(int i = 0;i<n/2;i++){
            int startR = i;

            for(int j = i;j<n-i-1;j++){
                int startC = j;
                int tempVal = matrix[startR][startC];

                int nowR = startR;
                int nowC = startC;

                while (true){
                    int tempR = nowR;
                    nowR = nowC;
                    nowC = n-1-tempR;

                    int temp = matrix[nowR][nowC];
                    matrix[nowR][nowC] = tempVal;
                    tempVal = temp;

                    if(nowR==startR&&nowC==startC)
                        break;

                }
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                System.out.print(matrix[i][j]+" ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        solution.rotate(new int[][]{{5,1,9,11},{2,4,8,10},{13,3,6,7},{15,14,12,16}});
    }


}
